package com.example.leetcode.trainingcamp.week9.sunday;

import java.util.*;

/**
 * 给定字典中的两个词，长度相等。写一个方法，把一个词转换成另一个词， 但是一次只能改变一个字符。每一步得到的新词都必须能在字典中找到。
 *
 * 编写一个程序，返回一个可能的转换序列。如有多个可能的转换序列，你可以返回任何一个。
 *
 * 示例 1:
 *
 * 输入:
 * beginWord = "hit",
 * endWord = "cog",
 * wordList = ["hot","dot","dog","lot","log","cog"]
 *
 * 输出:
 * ["hit","hot","dot","lot","log","cog"]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/word-transformer-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Offer17_22 {

    // 最短路径使用广度优先算法 bfs比较合适
    public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<String> result = new ArrayList<>();
        if (!wordList.contains(endWord)) return result;
        Queue<String> queue = new LinkedList<>();
        boolean[] visit = new boolean[wordList.size()];
        boolean is = false;
        Map<String,String> map = new HashMap<>();
        queue.add(beginWord);
        while (!queue.isEmpty()){
            String poll = queue.poll();
            if (poll.equals(endWord)){
                is = true;
                break;
            }
            for (int i =0;i<wordList.size();i++){
                if (!visit[i] && differ(poll,wordList.get(i))){
                    visit[i] = true;
                    queue.add(wordList.get(i));
                    map.put(wordList.get(i),poll);
                }
            }
        }
        if (!is) return result;
        String key = endWord;
        while (!map.get(key).equals(beginWord)){
            result.add(key);
            key = map.get(key);
        }
        result.add(key);
        result.add(map.get(key));
        Collections.reverse(result);
        return result;
    }



    public boolean differ(String s1,String s2){
        int count = 0;
        int len = s1.length();
        if (s2.length() != len) return false;
        for (int i =0;i<len;i++){
            if (s1.charAt(i) != s2.charAt(i)) count++;
        }
        return count == 1;
    }
}


class DemoOffer17_22{
    public static void main(String[] args) {
        String beginWord = "qa";
        String endWord = "sq";
        String[] strings = {"si","go","se","cm","so","ph","mt","db","mb",
                "sb","kr","ln","tm","le","av","sm","ar","ci","ca","br","ti","ba","to","ra","fa","yo","ow","sn","ya",
                "cr","po","fe","ho","ma","re","or","rn","au","ur","rh","sr","tc","lt","lo","as","fr","nb","yb","if","pb",
                "ge","th","pm","rb","sh","co","ga","li","ha","hz","no","bi","di","hi","qa","pi","os","uh","wm","an","me","mo","na","la"
                ,"st","er","sc","ne","mn","mi","am","ex","pt","io","be","fm","ta","tb","ni","mr","pa","he","lr","sq","ye"};
        List<String> wordList = new ArrayList<>(Arrays.asList(strings));
        Offer17_22 o = new Offer17_22();
        List<String> ladders = o.findLadders(beginWord, endWord, wordList);
        for (String s:ladders) {
            System.out.println(s);
        }
    }
}